package top.minuy.subject.leetcode._215;

import java.util.Random;

/**
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * @author Minuy
 * @time 08:29
 * @date 2021/9/2
 */
public class Solution {
    public int findKthLargest(int[] nums, int k) {

        if (k > nums.length) { // 如果不存在
            return -1;
        }

        // 输入的是找第k大的，转换成找第k小的
        k = nums.length-k;

        // 为分割做准备
        Random random = new Random();
        int l = 0, r = nums.length;

        do {
            // 获取随机隔断
            int rd = random.nextInt(r - l) + l;
            swap(nums, rd, l);

            // 三路快速排序算法
            // (l,tl)<V,[tl,i)=V,[i,tg]未处理,(tg,r-1]>V
            int i = l + 1, tl = l + 1, tg = r - 1;
            while (i <= tg) {
                if (nums[l] > nums[i]) {// 小于V的部分
                    swap(nums, i, tl);
                    tl++;
                    i++;
                } else if (nums[l] < nums[i]) {
                    swap(nums, i, tg);
                    tg--;
                } else { // 等于的部分
                    i++;
                }
            }
            swap(nums, tl - 1, l);
            tl--;
            tg++;

            // [l,tl)<V,  [tg,r)>V, [tl,tg) = V

            if (k >= tl && k < tg) {
                return nums[k];
            } else if (k < tl) {
                r = tl;
            } else {
                l = tg;
            }
        }
        while (true);
    }

    private void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}
